Năm 1987, Kim đã được phân công để đánh bom chuyến máy bay KAL 858. Bà được cho biết là mệnh lệnh đến trực tiếp từ chính lãnh tụ tối cao, Kim Il-sung. Bà được bảo là nếu bà thành công, bà sẽ có thể được trở lại và sống với gia đình mình và sẽ không phải làm việc như một điệp viên nữa. Bà một lần nữa lại làm việc chung với Kim Seung Il, người vừa hồi phục sau khi mổ dạ dày.

Kim đi lại với một hộ chiếu Nhật Bản giả dưới cái tên Mayumi Hachiya (蜂谷真由) cùng với Kim Seung Il, người đóng vai cha bà, lấy tên là Shinichi Hachiya (蜂谷真). Hai người đi sang châu Âu và cuối cùng gặp các điệp viên Triều Tiên khác ở Budapest, mà đã cung cấp cho họ với các vật liệu để hoàn thành sứ mệnh của mình. Kim Hyon-hui và Kim Seung Il đã để lại một quả bom (dấu trong một radio) trong cái giá để hành lý của chiếc máy bay KAL 858, khi họ xuống tại Abu Dhabi để đi đến Bahrain. Hai kẻ khủng bố tuy nhiên bị bắt tại Bahrain sau khi các nhân viên điều tra phát hiện ra, hộ chiếu của họ là giả. Kim Seung Il cắn một viên thuốc cyanide được dấu trong một điếu thuốc và chết. Kim Hyon-hui cũng định làm như vậy nhưng không thành công, khi một nữ cảnh sát Bahrain giật lấy điếu thuốc ra khỏi miệng bà khi bà bắt đầu ăn chất độc đó.[1][12] Bà đã phải nhập viện và sau đó bị thẩm vấn. Lúc đầu, bà nằng nặc nói tên mình là Pai Chui Hui, một đứa trẻ mồ côi từ miền Bắc Trung Quốc đã gặp một người đàn ông cao tuổi Nhật Bản mà cùng đi với bà. Tuy nhiên bà phủ nhận không có quan hệ tình dục gì cả với ông ta. Tuy nhiên, giọng bà nghe không giống như một người từ miền bắc Trung Quốc. Sau khi cơ quan an ninh Bahrain đã tin rằng bà ấy thực ra là một người Tiều Tiên, đã đưa bà bay đến Seoul, Hàn Quốc.[13]

Theo lời khai tại một buổi họp Hội đồng Bảo an Liên Hợp Quốc, Kim vào nhiều dịp đã được đưa đi để nhìn thấy sự thịnh vượng của Seoul bên ngoài nhà tù của bà. Các quan chức nhà tù cũng cho bà xem các chương trình truyền hình và những tường thuật tin tức cho thấy lối sống giàu có của người dân Hàn Quốc. Bà đã được dạy rằng miền Nam là một thái ấp đầy tham nhũng của Mỹ và sự nghèo đói rất phổ biến.[13]

Sau tám ngày, Kim đầu hàng, thừa nhận rằng bà trên thực tế là một người Triều Tiên và tiết lộ những chi tiết về vai trò của mình trong vụ đánh bom chuyến bay 858, cũng như dính líu của chính cá nhân Kim Il-sung trong chương trình này.